package hot;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Num301 {
    public static void main(String[] args) {
        Num301 n = new Num301();
        System.out.println(n.removeInvalidParentheses("()())()").toString());
    }
    Set<String> set = new HashSet<>();
    String res;
    int n,max,len;
    int l,r;
    public List<String> removeInvalidParentheses(String s) {
        res = s;
        n = s.length();
        for(char c : s.toCharArray()) {
            if(c == '(') {
                l++;
            }else if(c == ')'){
                if(l != 0) {
                    l--;
                }else {
                    r++;
                }
            }
        }
        len = n - l - r;
        int c1 = 0, c2 = 0;
        for(char c : s.toCharArray()) {
            if(c == '(') {
                c1++;
            }else if( c == ')'){
                c2++;
            }
        }
        max = Math.min(c1,c2);
        dfs(0,"",l,r,0);
        return new ArrayList<>(set);
    }
    public void dfs(int depth,String cur,int l,int r,int score) {
        if(l < 0 || r < 0 || score < 0 || score > max) return;
        if(l == 0 && r == 0) {
            if(cur.length() == len) set.add(cur);
        }
        if(depth == n) return;
        char c = res.charAt(depth);
        if(c == '(') {
            dfs(depth + 1,cur + String.valueOf(c),l,r,score + 1);
            dfs(depth + 1,cur,l - 1,r,score);
        }else if(c == ')') {
            dfs(depth + 1,cur + String.valueOf(c),l,r,score - 1);
            dfs(depth + 1,cur,l,r - 1,score);
        }else {
            dfs(depth + 1,cur + String.valueOf(c),l,r,score);
        }
    }
}
